import java.util.*;
public class Solution {
    //JZ43 整数中1出现的次数（从1到n整数中1出现的次数）
    public int NumberOf1Between1AndN_Solution(int n) {
        int count=0;
        for(int i=1;i<=n;i++){
            int j=i;
            while(j!=0){
                if(j%10==1){
                    count++;
                }
                j=j/10;
            }
        }
        return count;
    }
//JZ41 数据流中的中位数
    private ArrayList<Integer>a1=new ArrayList<>();
    public void Insert(Integer num) {
        //判断顺序表是否为空
        if(a1.isEmpty()){
            a1.add(num);
        }else{//不为空，让数组有序
            int i=0;
            for(;i<a1.size();i++){
                if(num<=a1.get(i)){
                    break;
                }
            }
            a1.add(i,num);
        }
    }

    public Double GetMedian() {
        int len = a1.size();
        if (len % 2 == 1) {
            int index = len / 2;
            return (double) a1.get(index);
        } else {
            int index = len / 2;
            double a = a1.get(index);
            double b = a1.get(index - 1);
            return (a + b) / 2;
        }
    }
    //JZ40 最小的K个数
    public ArrayList<Integer> GetLeastNumbers_Solution(
            int [] input, int k) {
        if(input.length==0||k<=0){
            return new ArrayList<Integer>();
        }
        //Top-k问题
        PriorityQueue<Integer>q1=new PriorityQueue<>(new Comparator<Integer>() {
            @Override
            public int compare(Integer o1, Integer o2) {
                return o2.compareTo(o1);
            }
        });
        //将k个元素建立大堆
        for (int i = 0; i <input.length ; i++) {
            if(i<k){
                q1.offer(input[i]);
            }else{//剩下K个元素分别和堆顶元素相比较。
                int val= q1.peek();
                if(input[i]<val){
                    //小于堆顶元素。出堆，input[i]入堆
                    q1.poll();
                    q1.offer(input[i]);
                }
            }
        }//将k个元素赋值到数组中
        ArrayList<Integer>a1=new ArrayList<>();
        while(!q1.isEmpty()){
            a1.add(q1.poll());
        }
        return a1;
    }
    //JZ34 二叉树中和为某一值的路径(二)
    class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;

        public TreeNode(int val) {
            this.val = val;
        }
    }
    private ArrayList<ArrayList<Integer>> ret=new ArrayList<>();
    protected Stack<Integer>q1=new Stack<>();
    void dfs(TreeNode root,int k){
        if(root==null){
            return;
        }
        q1.push(root.val);
        k=k-root.val;
        if(root.left==null&&root.right==null&&k==0){
            ret.add(new ArrayList<>(q1));
        }
        dfs(root.left,k);
        dfs(root.right,k);
        q1.pop();

    }
    public ArrayList<ArrayList<Integer>> FindPath(TreeNode root,int expectNumber) {
        dfs(root,expectNumber);
        return ret;
    }
    //JZ33 二叉搜索树的后序遍历序列
    public boolean VerifySquenceOfBST(int [] sequence) {
        //判断数组是否为空
        if(sequence.length==0){
            return false;
        }
        Stack<Integer> s1=new Stack<>();
        int root=Integer.MAX_VALUE;//整数的最大值
        int len=sequence.length-1;
        for(int i=len;i>=0;i--){
            if(sequence[i]>root){
                return false;
            }
            //这个while找到左右孩子的分届，之后再把左孩子
            //和根节点相比
            while(!s1.empty()&&s1.peek()>sequence[i]){
                root=s1.pop();
            }
            s1.push(sequence[i]);
        }
        return true;
    }
}